package ex.algorithms.heap;

import ex.util.CommonUtil;

public class Heap {
	public static void buildMaxHeap(int[] input) {
		if(input == null || input.length < 2)
			return;
		
		int node = input.length / 2;
		
		for(int i=node; i>= 1; i--)
			maxHeapify(input, i, input.length);
	}
	
	public static void maxHeapify(int[] input, int node, int length) {
		int leftIndex = 2*node;
		int rightIndex = 2*node + 1;
		
		int nextNode = node;
		
		if(leftIndex <= length && input[leftIndex - 1] > input[nextNode - 1]) {
			nextNode = leftIndex;
		}
		
		if(rightIndex <= length && input[rightIndex - 1] > input[nextNode - 1]) {
			nextNode = rightIndex;
		}
		
		if(nextNode != node) {
			CommonUtil.swap(input, nextNode-1, node-1);
			maxHeapify(input, nextNode, length);
		}
		
	}
}
